A number of algorithms or methods for locating a particular element within a list of elements are well known in the prior art. Such algorithms include the binary search algorithm, the hash search algorithm and the linear search algorithm. A list which is searched using a linear search algorithm need not be ordered, but linear searches suffer from an inherent inefficiency as a key value must be compared to each and every potential target value in the list until the target value is located. A binary search (also termed a "binary chop" or "dichotomizing" search) is more efficient than a linear search, but requires that the list of elements being searched be ordered. Specifically, a binary search may involve comparing a key value against values in a list of values which are arranged in a known sequence, such as an ascending or descending order. The binary search begins by comparing the key value against a value in the middle of the list. If the key value is found to be greater than that middle value, half of the list can be discarded, and the search algorithm is then performed on the remaining half of the list. The key value is then again compared to a value in the middle of the remaining half-list, which may then again be divided into a discarded quarter-list and a remaining quarter-list. By iteratively performing this process, the key value is compared against a value in the middle of succeedingly smaller lists, and the target value is located in this manner. It will be appreciated that, as the key value is not compared against each and every value in the list, a binary search achieves a higher degree of efficiency than a linear search.
The maintenance of an ordered list of elements on which a binary search may be conducted presents a number of potential inefficiencies when elements are routinely added to or subtracted from the list which is searched. Specifically, a value being added to an ordered list must be entered into a location within the list so as to preserve the ordered nature thereof. Similarly, the removal of a value from the list must be done in a manner so as to preserve the ordered nature thereof. Accordingly, the addition of a value into an ordered list typically requires that all values greater (or less) than the inserted value be displaced within a memory resource, and shifted by a location within the memory resource, to thereby expand the list to accommodate the inserted value. Where the relevant list is of a substantial length, this displacement of values above (or below) an insertion point to accommodate an inserted value can be particularly time consuming.
It may occur that a search of a list is requested very soon after an update operation (i.e. either a value insertion or removal operation) is commenced. In one prior art methodology, access to the ordered list for search purposes is blocked during an update operation. As stated above, where a list is of a substantial length, an update operation may be time consuming, and a requested search operation will thus be forced to wait until the list has been updated prior to being serviced. Causing the search operation to wait for completion of an update operation reduces the efficiency of the entity performing the search.
In an attempt to address the above identified inefficiency, a prior art solution proposes maintaining two copies of a searchable list. An update operation is performed on a first copy of the list, while the second copy is made available to search operations. On conclusion of the update operation, the updated list is then brought "on-line" and made searchable, while the second list is taken "off-line" and updated to correspond to the first list. However, this solution suffers from the drawback of requiring that capacity be provided in a memory resource for the maintenance of two lists. Again, where a list is of considerable length, the occupation of storage capacity by the second ordered list may be undesirable.
The above difficulties with the maintenance of an ordered list have resulted in the binary search methodology being abandoned in many time-sensitive applications in favor of other search methodologies, such as the hashing methodology. However, such alternative search methodologies present their own inherent problems.